1. Field of the Invention
The present invention relates to the compression of periodic halftoned digital images. More particularly, the invention concerns a way to increase the compression ratio obtained on periodic halftones using commonly known compression components, while reducing the time required to perform the compression.
2. Description of the Related Art
Data compression is a process of finding the most efficient way to represent a message in order to minimize the size of a message for transfer or storage. Data compression usually consists of two phases--choosing a model for the message source and designing an efficient coding system for the model.
A message generated by an information source may take on many possible forms depending upon the context in which the message was made, and the goal of compressed communication in general is to transmit the minimal encoded version of the original message such that the receiver of the message can still reconstruct it. For example, the information to be sent may be the results of a bicycle race. If the recipient of the message already knows the names and numbers of the cyclists, then all that must be transferred is the number of the cyclist that won. In another context, the number might mean something entirely different, such as the price of a dozen mangoes. Accordingly, the key to quick and effective compressed communication is minimizing the length of information that must be transferred to accurately send the correct message or in the case of a photograph, the correct image. Thus, the shortest representation of the source of the message--so that the message can be taken in context--and the message itself is critical to efficient compressed communications.
Generally, if each piece of information sent representing a message or image is not equally likely to occur it is more efficient on the average to allocate a short string to frequently occurring pieces of information and longer strings to less frequent pieces. Thus, Morse code allots the shortest string (a dot and pause) to the letter "e" because it appears most frequently in words, and allots a long string (dash, dash, dot, dot and pause) to the less frequently appearing letter "z."
One important area in data compression is the compression of periodic halftoned bilevel digital (halftoned) images used predominantly to prepare continuous tone photographic images for bitonal printing. Continuous tone (e.g., monochrome) photographs are transformed into a bitonal (e.g., black/white) "halftoned" equivalent, which in digital form is represented as a bilevel (e.g., "1" or "0" valued) image. Numerous methods used primarily for textual image compression have been attempted for compressing such bilevel halftoned images. For example, one-dimensional schemes, such as Modified Huffman (MH) coding, or two-dimensional schemes, such as the Modified Relative Element Address Designate (MR)--commonly referred to as the CCITT Group 3 compression scheme--are simple and efficient but unable to effectively compress halftoned images.
The MR coding method exploits vertical correlation between scan lines in textual images by attempting to code all black/white pixel color changes (BW edges) and white/black pixel color changes (WB edges) in an image with respect to a given reference edge located directly above in a previous line. If such coding fails or is not reproductable at a decoder. the method changes to an MH coding method, which uses alternating sequential run-length coders for alternating black and white runs. Note that this also equates to coding alternating BW and WB edge positions.
The MMR or Modified MR two-dimensional compressor coding method, widely known as the CCITT Group 4 compression scheme removes some error protection overhead from the MR coding method but is still unable to effectively compress halftoned images.
The problem with these one- and two-dimensional coding schemes for halftoned encoding is that binary halftoned representations of continuous tone images have very different distributions of run size and occurrences of vertical references from the text or line drawing images for which these schemes were designed. As a result, the amount of data required to represent halftoned images in "compressed" form when these schemes are used, may actually be greater than the amount of data required to represent the original uncompressed image.
Recently, complex adaptive coding methods like various Ziv-Lempel algorithms and the arithmetic coding based Joint Bi-level Image Experts Group (JBIG) algorithm as set forth in ITU-T Recommendation T.82, "Information Technology--Coded Representation of Picture and Audio Information--Progressive Bi-level Image Compression," have been developed which arc aimed at compressing both textual and halftoned images. Unlike static algorithms like MH, MR or MMR used for textual images, these adaptive algorithms can adjust to the more balanced white and black pixel probabilities and shorter run length characteristics of halftoned images. The problem is that these adaptive algorithms arc not simple nor fast enough to replace the above static algorithms in software. For example, the Ziv-Lempel algorithms build complex dictionaries or alternatively perform complex dictionary searches in real time. Typically, they also exploit byte-oriented characteristics rather than the bit-oriented characteristics of bitonal images. Although byte-processing makes the Ziv-Lempel algorithms faster in compressing bitonal images than adaptive arithmetic coding methods such as JBIG methods, these algorithms are not as fast as MH, MR or MMR. Furthermore, although JBIG will compress halftoned images much better than the Ziv-Lempel algorithms, it is even more complex and even slower in executing.
These above methods for compressing halftoned images constitute significant advances and enjoy widespread commercial success today. But what is needed is a simple and efficient method and apparatus for compressing halftoned images that increases compression ratios and decreases the time required to perform the compression over the commonly used MH, MR or MMR coding methods.